package com.cdream.basic.algorithm.leetcode.bfs;

import java.util.*;
import java.util.stream.Collectors;

/**
 * @author cdream
 * @date 2022/1/29
 */
public class Question1765 {
    int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        new Question1765().highestPeak(new int[][]{{0, 1}, {0, 0}});
    }

    public int[][] highestPeak(int[][] isWater) {
        int x = isWater.length;
        int y = isWater[0].length;

        int[][] high = new int[x][y];
        for (int i = 0; i < x; i++) {
            Arrays.fill(high[i], -1);
        }
        LinkedList<int[]> list = new LinkedList<>();
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (isWater[i][j] == 1) {
                    high[i][j] = 0;
                    list.offer(new int[]{i, j});
                }
            }
        }

        while (!list.isEmpty()) {
            int[] p = list.poll();
            int px = p[0];
            int py = p[1];
            for (int[] dir : dirs) {
                int npx = px + dir[0];
                int npy = py + dir[1];
                if (npx >= 0 && npx < x && npy >= 0 && npy < y && high[npx][npy] == -1) {
                    high[npx][npy] = high[px][py] + 1;
                    list.offer(new int[]{npx, npy});
                }
            }
        }
        return high;
    }

    public String[] uncommonFromSentences(String s1, String s2) {
        String[] str1 = s1.split(" ");
        String[] str2 = s2.split(" ");
        Map<String, Long> map1 = Arrays.stream(str1).collect(Collectors.groupingBy(a -> a, Collectors.counting()));
        Map<String, Long> map2 = Arrays.stream(str2).collect(Collectors.groupingBy(a -> a, Collectors.counting()));
        List<String> res = new ArrayList<>();
        map1.forEach((k,v)->{
            if (v==1 && !map2.containsKey(k)){
                res.add(k);
            }
        });
        map2.forEach((k,v)->{
            if (v==1 && !map1.containsKey(k)){
                res.add(k);
            }
        });
        return res.toArray(new String[]{});
    }
}
